Note that this is not part of the Playlist. See the textbook, chapter 7 instead.

In Chapter Four we discussed \(n\)-step TD algorithms, where we take the trace of the next \(n\) rewards for a state and accumulating into a single update.

However, we may combine multiple traces, for each \(n\). In particular, we shall combine all possible traces, weighting geometrically by a \(\lambda\) parameter.

For example, for a reward \(r_t\), we shall acredit it to the states preceding it.

• \(a_t\) gets \(\lambda\) of the credit
• \(a_{t-1}\) gets \(\lambda^2\) of the credit
• \(\ldots\)

This allows for a smoother convergence (from being similar to MC) while also being quick to train (being similar to TD). Note that choosing lambda, it may approach MC (\(\lambda = 1\)), or it may approach \(1\)-step TD (\(\lambda = 0\)).

A state \(s\) is eligibile to receive accreditation for a reward when it was visited. In particular (for accumulating traces), we define an \(E\) vector, s.t.

\begin{align} E(s_t) &\xleftarrow{} \gamma \lambda (E(s_t) + 1) \\ E(s \ne s_t) &\xleftarrow{} \gamma \lambda E(s) \\ \end{align}

Thus, we have the following algorithm:

• Initialize \(E(s) \xleftarrow{} 0, \forall s\)
• Repeat for each step of each episode
  • Update \(E(S)\)
  • \(\delta \xleftarrow{} g^{(m)}_t - v(s^{(m)}_t)\)
  • \(v(s^{(m)}_t) \gets v(s^{(m)}_t) + \alpha \delta E(s^{(m)}_t)\)

In the continuous case, we do not accumulate eligiblity for states, as each individual state has no impact. Thus, we only decay traces.

• \(E \xleftarrow{} 0\)
• Repeat for each step of each episode
  • \(E \gets \gamma \lambda E + \nabla v(s^{(m)}_t, w)\)
  • \(\delta \xleftarrow{} g^{(m)}_t - v(s^{(m)}_t, w)\)
  • \(w \gets w + \alpha \delta E\)

Home 1 2 3 4(b) 5 6